package com.linchong.stackqueue.easy;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-05 9:58
 * @Description: ValidParentheses$
 * <p>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "()[]{}"
 * 输出: true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 */
public class ValidParentheses {

	public boolean isValid(String s) {
		int n = s.length();
		if (n <= 1 || n % 2 != 0) {
			return false;
		}
		Stack<Character> stack = new Stack<>();
		char[] chars = s.toCharArray();
		Map<Character, Character> map = new HashMap<>(3);
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
		for (int i = 0; i < n; i++) {
			char chr = chars[i];
			if (map.containsKey(chr)) {
				stack.push(chr);
			} else{
				if(stack.isEmpty()||chr!=map.get(stack.pop())) {
						return false;
				}
			}
		}
		return stack.isEmpty();
	}

	public static void main(String[] args) {
		String s = "))";
		ValidParentheses instance = new ValidParentheses();
		System.out.println(instance.isValid(s));
	}
}
